package uba.algo3.tp3.tsp;

import java.util.ArrayList;

public class BusquedaLocal {
	
	private Grafo g;
	private Constructiva constructiva;
	int costoMin = Integer.MAX_VALUE;
	int toleranciaOriginal = 100000; //ver si usamos esto o no, o si ponemos otro valor
	
	public Grafo getG()
	{
		return g;
	}

	public void setG(Grafo g)
	{
		this.g = g;
	}
	
	public BusquedaLocal(Grafo g)
	{
        this.g = g;
	}
	
	public Solucion get2TSP()
	{
		constructiva = new Constructiva(getG());
		Solucion mejorSol = constructiva.get2TSP(); //mejor solucion hasta el momento
		
		do{
			
			ArrayList<Integer> vecina2, vecina1;
			int tamPart1 = mejorSol.getCiclo1().size();
			int tamPart2 = mejorSol.getCiclo2().size();
			int max, maxOriginal, costoVecina, temp;
			boolean encontreMejorSolucion = false;
			Solucion mejorSolOriginal = new Solucion((ArrayList<Integer>) mejorSol.getCiclo1().clone(), (ArrayList<Integer>) mejorSol.getCiclo2().clone(), mejorSol.getCosto());
			Solucion vecina = null;
			
			if(tamPart1 < tamPart2)//Siempre vamos a tener la solucion mas grande en el ciclo1
			{
				max = tamPart2;
				maxOriginal = tamPart2;
				
				temp = tamPart1;
				tamPart1 = tamPart2;
				tamPart2 = temp;
				/* cambio el orden de los ciclos, esto es para que se prueben todas las combinaciones posibles
				 *  cuando intercambiamos nodos entre diferentes ciclos */
				mejorSol.cambiarCiclos();
			}
			else
			{
				max = tamPart1;
				maxOriginal = tamPart1;
			}
			
			
			for(int k = 0; k < maxOriginal - 2;k++)
			{
				
				for(int i = 1; i < max; i++)
				{
					for(int j = 1; j < max; j++)
					{
						vecina1 = mejorSol.getCiclo1();
						vecina2 = mejorSol.getCiclo2();
						
						if(vecina1.size() < vecina2.size())
						{
							ArrayList<Integer> vecinaTemp = vecina1;
							vecina1 = vecina2;
							vecina2 = vecinaTemp;
							tamPart1 = vecina1.size();
							tamPart2 = vecina2.size();
						}
						
						if(i != j)
						{
							
								if(i < tamPart2 && j < tamPart2) //swapeo de los nodos del ciclo2
								{
									swap(vecina2,i,j);
									costoVecina = g.calcular_costo(vecina1) + g.calcular_costo(vecina2);
									
									//Si es mejor solucion, paro de buscar soluciones vecinas y cambio la mejor solucion
									if(costoVecina < mejorSol.getCosto())
									{
										vecina = new Solucion(vecina1,vecina2,costoVecina);
										encontreMejorSolucion = true;
										break;
									}
									else
									{
										swap(vecina2,j,i);
									}
			
								}
								
								if(i < tamPart1 && j < tamPart1) //swapeo de los nodos del ciclo1
								{
									swap(vecina1,i,j);
									costoVecina = g.calcular_costo(vecina2) + g.calcular_costo(vecina1);
									
									if(costoVecina < mejorSol.getCosto())
									{
										vecina = new Solucion(vecina1, vecina2,costoVecina);
										encontreMejorSolucion = true;
										break;
									}
									else
									{
										swap(vecina1,j,i);
									}
								}
						}
						
						if(j < tamPart1 && i < tamPart2)
						{
							swap(vecina1,vecina2,i,j);
							costoVecina = g.calcular_costo(vecina1) + g.calcular_costo(vecina2);
							
							//SI ES MEJOR SOLUCION HAGO BREAK, ME GUARDO LA SOL, Y HAGO BREAK DE NUEVO
							if(costoVecina < mejorSol.getCosto())
							{
								vecina = new Solucion(vecina1, vecina2,costoVecina);
								encontreMejorSolucion = true;
								break;
							}
							else
							{
								swap(vecina1,vecina2,i,j);
							}
						}
						
					}
					
					if(encontreMejorSolucion)
					{
						mejorSol = vecina;
						break;
					}
				}
				
				if(encontreMejorSolucion)
				{
					mejorSol = vecina;
					break;
				}

				ArrayList<Integer> ciclo1 = mejorSol.getCiclo1();
				ArrayList<Integer> ciclo2 = mejorSol.getCiclo2();
				Integer t = ciclo1.get(1);//Elegimos el primero ya que despues hacemos todas los swapeos posibles
				ciclo1.remove(1);
				ciclo2.add(t);
				
				tamPart1 = ciclo1.size();
				tamPart2 = ciclo2.size();

			}
			if(encontreMejorSolucion){ //encontre una solucion mejor a la que tenia
				encontreMejorSolucion = false;
			}else{
				mejorSol = mejorSolOriginal;//Estoy atascado en un minimo local, salgo
				break;
			}
		}while(true);
		
		return mejorSol;
	}
	
	
	
	
	
	private void swap(ArrayList<Integer> v1, ArrayList<Integer> v2,
			int i, int j)
	{
		Integer temp = v1.get(j);
        v1.set(j,v2.get(i));
        v2.set(i,temp);

	}
	
	private void swap(ArrayList<Integer> a, int i, int j){
		Integer temp = a.get(i);   
        a.set(i,a.get(j));
        a.set(j,temp);
	}
	
}